// #include <stdio.h>
// #include <stdlib.h>
// #include <stdbool.h>
// #include <time.h>
//
// #include "windows.h"
//
// typedef int DataType;
//
// typedef struct TreeNode {
//     DataType value;
//     struct TreeNode* left;
//     struct TreeNode* right;
// } TreeNode;
//
// typedef struct QNode {
//     TreeNode* data;
//     struct QNode* next;
// }QNode;
//
// typedef struct Queue {
//     QNode* front;
//     QNode* rear;
// }Queue;
//
// // 创建新节点
// TreeNode* CreateNode(DataType value) {
//     TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
//     if (newNode == NULL) {
//         perror("Memory allocation failed");
//         exit(EXIT_FAILURE);
//     }
//     newNode->value = value;
//     newNode->left = newNode->right = NULL;
//     return newNode;
// }
//
// // 插入节点（二叉搜索树规则）
// TreeNode* InsertNode(TreeNode* root, DataType x) {
//     if (root == NULL) {
//         return CreateNode(x);
//     }
//     if (x < root->value) {
//         root->left = InsertNode(root->left, x);
//     } else {
//         root->right = InsertNode(root->right, x);
//     }
//     return root;
// }
//
// //先序遍历
// void PreOrder(TreeNode* root) {
//     if(root) {
//         printf("%d ",root->value);
//         PreOrder(root->left);
//         PreOrder(root->right);
//     }
// }
//
// // 释放内存
// void FreeTree(TreeNode* root) {
//     if (root) {
//         FreeTree(root->left);
//         FreeTree(root->right);
//         free(root);
//     }
// }
//
// //申请队列节点
// QNode* ApplyQueueNode(TreeNode* node) {
//     QNode* newnode=(QNode*)malloc(sizeof(QNode));
//     if(newnode==NULL) {
//         exit(1);
//     }
//     newnode->data=node;
//     newnode->next=NULL;
//     return newnode;
// }
//
// //初始化队列
// void InitQueue(Queue* q) {
//     q->front=q->rear=NULL;
// }
//
// //判断空
// int IsQueueNull(Queue* q) {
//     return (q->front==NULL&&q->rear==NULL);
// }
//
// //入队
// void EnQueue(Queue* q,TreeNode* node) {
//     if(q==NULL) {
//         return;
//     }
//     QNode* tmp=ApplyQueueNode(node);
//     if(IsQueueNull(q)) {
//         q->front=q->rear=tmp;
//     }else {
//         q->rear->next=tmp;
//         q->rear=tmp;
//     }
// }
//
// //出队
// TreeNode* DeQueue(Queue* q) {
//     if(IsQueueNull(q)) {
//         return NULL;
//     }
//     QNode* tmp=q->front;
//     q->front=q->front->next;
//     TreeNode* p=tmp->data;
//     if(q->front==NULL) {
//         q->rear=NULL;
//     }
//     free(tmp);
//     return p;
// }
//
// //删除字树
// void FreeSonTree(TreeNode* root) {
//     if(root) {
//         FreeSonTree(root->left);
//         FreeSonTree(root->right);
//         free(root);
//     }
// }
//
// //查找为x值的节点,删除x值为根的字树
// void FreeXRootTree(TreeNode* root,DataType x) {
//     Queue q;
//     if(root) {
//         if(root->value==x) {
//             FreeSonTree(root);
//             exit(1);
//         }
//         InitQueue(&q);
//         EnQueue(&q,root);
//         while (!IsQueueNull(&q)) {
//             TreeNode* p=DeQueue(&q);
//             if(p->left) {
//                 if(p->left->value==x) {
//                     FreeSonTree(p->left);
//                     p->left=NULL;
//                 }else {
//                     EnQueue(&q,p->left);
//                 }
//             }
//             if(p->right) {
//                 if(p->right->value==x) {
//                     FreeSonTree(p->right);
//                     p->right=NULL;
//                 }else {
//                     EnQueue(&q,p->right);
//                 }
//             }
//         }
//     }
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     TreeNode* root = NULL;
//     int values[] = {50, 30, 70, 20, 40, 60, 80};
//     int length = sizeof(values) / sizeof(values[0]);
//
//     // 构建二叉搜索树
//     for (int i = 0; i < length; i++) {
//         root = InsertNode(root, values[i]);
//     }
//
//     PreOrder(root);printf("\n");
//     FreeXRootTree(root,70);
//     PreOrder(root);printf("\n");
//
//     FreeTree(root);
//     return 0;
// }